Counting Distinct Objects over Sliding Windows

Zhang, W., Zhang, Y, Cheema, M. A. and Lin, X.

Aggregation against distinct objects has been involved in many real applications with the presence of duplicates, including real-time monitoring moving objects. In this paper, we investigate the problem of counting distinct objects over sliding windows with arbitrary lengths. We present novel, time and space efficient, one scan algorithms to continuously maintain a sketch so that the counting can be approximately conducted with a relative error guarantee ǫ in the presence of object duplicates. Efficient query algorithms have also been developed by effectively utilizing the skyband property. Moreover, the proposed techniques may be immediately applied to the range counting aggregation and heavy hitter problem against distinct elements. A comprehensive performance study demonstrates that our algorithms can support real-time computation against high speed data streams.

Cite as: Zhang, W., Zhang, Y, Cheema, M. A. and Lin, X. (2010). Counting Distinct Objects over Sliding Windows. In Proc. 21st Australasian Database Conference (ADC 2010) Brisbane, Australia. CRPIT, 104. Shen H.T. and Bouguettaya, A. Eds., ACS. 75-84

(from crpit.com) (local if available)